package org.wyw.solution;

@Solution(
        id = 4,
        title = "买股票的最佳时机",
        difficulty = "medium",
        link = "https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/description/"
)
public class Solution004 {
    /**
     * 思路：假设第一天是最低价格，最大利润是0，从第二天起，遍历数组，
     * 每次比较出当前最低价格，并计算当前价格的利润，与最大利润比较
     */
    public int maxProfit(int[] prices) {
        int minPrice = prices[0];
        int maxProfit = 0;
        for (int i = 1; i < prices.length; i++) {
            int price = prices[i];
            //若当前值比最小值小则更新最小值，否则当前值就不是最小值，可能是利润，并和已有的最大利润比较，更新真正的最大利润
            if (price < minPrice) {
                minPrice = price;
            } else {
                maxProfit = Math.max(maxProfit, price - minPrice);
            }
        }
        return maxProfit;
    }
}
